package site.wanjiahao;

/**
 * 布隆过滤器可以解决缓存穿透问题
 * @param <T>
 */
public class BloomFilter<T> {

    /**
     * 二进制向量长度
     */
    private int bitSize;

    /**
     * 二进制向量
     */
    private long[] bits;

    /**
     * 哈希函数个数
     */
    private int hashSize;

    /**
     * 根据元素个数和误判率求得二进制向量个数，和hash函数的个数
     * @param count 存储元素个数
     * @param p 误判率大小
     */
    public BloomFilter(int count, double p) {
        if (count <= 0 || p <= 0 || p >= 1) {
            throw new IllegalArgumentException("wrong n or p");
        }
        double ln2 = Math.log(2);
        // 求出二进制向量个数
        bitSize = (int) -(count * Math.log(p) / (ln2 * ln2));
        // hash函数的个数
        hashSize = (int) (bitSize * ln2 / count);
        // 求出long数组的长度 向上取整
        bits = new long[(bitSize + Long.SIZE - 1) / Long.SIZE];
    }

    /**
     * 添加元素
     * @return true代表当前位发生了变化
     */
    boolean put(T value) {
        nullCheck(value);
        // 生成对应次数的hash函数
        int hash1 = value.hashCode();
        int hash2 = hash1 >>> 16;
        boolean result = false;
        for (int i = 0; i < hashSize; i++) {
            int combineHash = hash1 + (i * hash2);
            if (combineHash < 0) {
                combineHash = ~combineHash;
            }

            // 取模，获取元素索引位置
            int index = combineHash % bitSize;
            if (set(index)) result = true;
        }
        return result;
    }

    boolean contains(T value) {
        nullCheck(value);
        // 生成对应次数的hash函数
        int hash1 = value.hashCode();
        int hash2 = hash1 >>> 16;
        for (int i = 0; i < hashSize; i++) {
            int combineHash = hash1 + (i * hash2);
            if (combineHash < 0) {
                combineHash = ~combineHash;
            }

            // 取模，获取元素索引位置
            int index = combineHash % bitSize;
            if (!get(index)) return false;
        }
        return true;
    }

    // 设置对应index位置的二进制位为true
    private boolean set(int index) {
        long value = bits[index / Long.SIZE];
        int bitValue = (1 << (index % Long.SIZE));
        if ((value & bitValue) == 0) {
            // 需要变为1
            bits[index / Long.SIZE] = value | bitValue;
            return true;
        }
        return false;
    }

    /**
     * 查看index对应的二进制位的信息
     * @param index index索引
     * @return 返回值
     */
    private boolean get(int index) {
        long value = bits[index / Long.SIZE];
        // 查看对应的二进制的信息
        return (value & (1L << (index % Long.SIZE))) != 0;
    }

    private void nullCheck(T value) {
        if (value == null) {
            throw new IllegalArgumentException("Value must not be null.");
        }
    }

}
